/* 
 * Copyright (C) 2013 Milind Dumbare <milind.dumbare@gmail.com>
 */
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;

/* max size for stack/queue */
#define MAXSIZE 100

/* Forward declaratios */
class stack2;
class stack;
class hash_t;
class queue;

/* class around tokens we generate out of input string.
 *  friend function parse() accesses the array(word) of std::string and no_of_words" variable.
 */
class expression
{
public:
	std::string *word;
	int no_of_words;
	expression(char*);
	~expression();
	friend int parse(expression& exp, hash_t& hash, queue& xqueue, stack2& xstack2);
};

expression::~expression()
{
		delete []word;
}

/* constructor of expression class 
 * 
 * tokenize the input array and save it in word[]
 *
 * also set no_of_words to number of words in "word"
 */
expression::expression(char* str)
{
	double number;
	char* token;
	int i = 1;
	int len = 0;
	
	word = new std::string[MAXSIZE];
	if ((token = strtok(str, " ")) != NULL) {
		word[0].assign(token);
		while ((token = strtok(NULL, " ")) != NULL) {
			word[i].assign(token);
			i++;
			if ( i == (MAXSIZE -1)) {
				cout << "Too long expression\n";
				exit(1);
			}
				
		}
	}
	no_of_words = i;
}
/* queue for postfix expression */
class queue;
	struct hash_table_token {
		std::string *str;
		double value;
		struct hash_table_token *next;
	};

struct hash_table {
	struct hash_table_token *tok;
};
/* Hash table of strings of numerics.
 */
class hash_t
{

	struct hash_table hash_table[7];
public:
	hash_t();
	~hash_t();
	double find_string_in_hash_table(std::string);
	void build_hash_table_row(const std::string* db, int *db_val, int row, int no_strings);
	friend int parse(expression& exp, hash_t& hash, queue& xqueue, stack2& xstack2);
};

void hash_t::build_hash_table_row(const std::string* db, int *db_val, int row, int no_strings)
{
        struct hash_table_token *tok, *temp_tok;
        int i;

        tok = (struct hash_table_token *)malloc(sizeof(struct hash_table_token));
	tok->str = new std::string();
        tok->str->assign(db[0]);
        tok->value = db_val[0];
        tok->next = NULL;
        hash_table[row].tok = tok;
        for(i = 1; i < no_strings; i++) {
                temp_tok = (struct hash_table_token *)malloc(sizeof(struct hash_table_token));
		temp_tok->str = new std::string();
                tok->next = temp_tok;
                temp_tok->str->assign(db[i]);
                temp_tok->value = db_val[i];
                tok = temp_tok;
        }
        temp_tok->next = NULL;
}
hash_t::~hash_t()
{
	int i;
	struct hash_table_token *tok, *temp_tok;
	for(i = 0; i < 7; i ++) {
		tok = hash_table[i].tok;
		while (tok != NULL) {
			temp_tok = tok->next;
			delete tok->str;
			free(tok);
			tok = temp_tok;
		}
	}
}

hash_t::hash_t()
{
/*
 * Hash table is arranged according to the length of the numeric word 
 * There are 7 lenghts of words so hash table is of 7 rows.
 *  Indexing function is as simple as fn(length - 3)
 *
 *	hash[0] = {"one", "two", "six", "ten"};
 *	hash[1] = {"four", "five", "nine"};
 *	hash[2] = {"three", "seven", "eight", "fifty", "sixty"};
 *	hash[3] = {"eleven", "twelve", "twenty", "thirty", "fourty", "eighty", "ninety"};
 *	hash[4] = {"fifteen", "sixteen", "ninteen", "seventy"};
 *	hash[5] = {"thirteen", "fourteen", "eighteen"};
 *	hash[6] = {"seventeen"};
*/
	std::string db_len_3[4] = {"one", "two", "six", "ten"};
	int db_len_3_val[4] = { 1, 2, 6, 10 };
	std::string db_len_4[3] = {"four", "five", "nine"};
	int db_len_4_val[3] = { 4, 5, 9 };
	std::string db_len_5[5] = {"three", "seven", "eight", "fifty", "sixty"};
	int db_len_5_val[5] = { 3, 7, 8, 50, 60 };
	std::string db_len_6[7] = {"eleven", "twelve", "twenty", "thirty", "fourty", "eighty", "ninety"};
	int db_len_6_val[7] = { 11, 12, 20, 30, 40, 80, 90 };
	std::string db_len_7[4] = {"fifteen", "sixteen", "ninteen", "seventy"};
	int db_len_7_val[4] = { 15, 16, 19, 70 };
	std::string db_len_8[3] = {"thirteen", "fourteen", "eighteen"};
	int db_len_8_val[3] = { 13, 14, 18 };
	std::string db_len_9[1] = {"seventeen"};
	int db_len_9_val[1] = { 17 };

        /* string db, value db, row, no_strings */
        build_hash_table_row(db_len_3, db_len_3_val, 0, 4);
        build_hash_table_row(db_len_4, db_len_4_val, 1, 3);
        build_hash_table_row(db_len_5, db_len_5_val, 2, 5);
        build_hash_table_row(db_len_6, db_len_6_val, 3, 7);
        build_hash_table_row(db_len_7, db_len_7_val, 4, 4);
        build_hash_table_row(db_len_8, db_len_8_val, 5, 3);
        build_hash_table_row(db_len_7, db_len_7_val, 4, 4);
        build_hash_table_row(db_len_8, db_len_8_val, 5, 3);
        build_hash_table_row(db_len_9, db_len_9_val, 6, 1);
}

double hash_t::find_string_in_hash_table(std::string str)
{
	/* get the length to index into hash table */
	int len = str.length();
        struct hash_table_token *tok;
        tok = hash_table[len-3].tok;

        while(tok != NULL) {
		/* iterate in the hash table's row till we find our string */
                if (str.compare(*tok->str) == 0) {
                        return tok->value;
                }
                tok = tok->next;
        }
	/* if here that means there was a string of matching length but its not 
 	 * a valid string */
	return -1;

}

/*========= postfix expression queue  ==============*/
/* if have number then set type = 1 in struct queue_node and set value.number in the union 
 * if have operator then set type = 2 in struct queue_node and set valu.operator in the union
 */
union val {
        double number;
        std::string *opertor;
};

struct queue_node {
        int type; /* 1 if double 2 if char* */
        union val value;
};
/* Queue for postfix expression
 * Queue can have numbers(digits) as well as operators (+, -, *, /)
 */
class queue
{
	struct queue_node queu[MAXSIZE];
	int front, rear;
	int isempty();
	int isfull();
public:
	void enqueue(struct queue_node node);
	struct queue_node dequeue();
	queue();
	friend void generate_postfix_queue(stack2& xstack2, queue& xqueue, char* str);
	friend int parse(expression& exp, hash_t& hash, queue& xqueue, stack2& xstack2);
	friend void queue_all_operators_to_postfix(stack2& xstack2, queue& xqueue);
	friend double solve_the_postfix(queue xqueue, stack xstack);
};

/* Queue constructor.
 */
queue::queue()
{
	front = rear = 0;
}

/* return 
 * 1: if queue full
 * 0: if not
 */
int queue::isfull()
{
	return (rear == MAXSIZE - 1 );
}
/* return 
 * 1: if queue empty
 * 0: if not
 */
int queue::isempty()
{
	return (front == rear);
}

/* returns nothing
 */
void queue::enqueue(struct queue_node node)
{
        if (!isfull()) {
                rear = rear + 1;
		/* find the type of data (number/operator) and enqueue it 
 		 * in proper place in the union */
                if (node.type == 1) {
                        queu[rear].type = 1;
                        queu[rear].value.number = node.value.number;
                } else {
                        queu[rear].type =2;
			queu[rear].value.opertor = new std::string;
                        queu[rear].value.opertor->assign(node.value.opertor->c_str());
                }

        } else {
		cout<<"queue is full\n"<<endl;
		exit(1);
	}
}
/* returns queue node */
struct queue_node queue::dequeue()
{
	if(!isempty()) {
		return queu[++front];
	} else {
		cout<<"queue is empty"<<endl;
		exit(1);
	}
}
/*========= postfix expression queue ends ==============*/

/*========= operand stack ==============*/
class stack
{
	double stck[MAXSIZE];
	int top;
	int isempty();
	int isfull();
public:
	stack();
	void push(double val);
	double pop();
	friend double solve_the_postfix(queue xqueue, stack xstack);
};

stack::stack()
{
	top = 0;
}

int stack::isempty()
{
	return !top?1:0;
}

int stack::isfull()
{
	return (top == MAXSIZE)?1:0;
}
	
void stack::push(double val)
{
	if (isfull()) {
		cout<<"stack full\n"<<endl;
	} else {
		stck[++top] = val;
	}
}

double stack::pop()
{
	if (isempty()) {
		cout<<"stack empty\n"<<endl;
	} else {
		return stck[top--];
	}
}
/*========= operand stack ends ==============*/

/*========= operator stack ends ==============*/
class stack2
{
	std::string* stck2[MAXSIZE];
	int top;
public:
	stack2();
	int isempty();
	void push(std::string* opertor);
	std::string* pop();
	int isfull();
	int precedence_of_top();
	friend void generate_postfix_queue(stack2& xstack2, queue& xqueue, char* str);
	friend int parse(expression& exp, hash_t& hash, queue& xqueue, stack2& xstack2);
	friend void queue_all_operators_to_postfix(stack2& xstack2, queue& xqueue);
};
/* Calculate precedence of the operator which is on the top of stack.
 * This is required in generating the postfix queue of the expression */
int stack2::precedence_of_top()
{
        if ((stck2[top]->compare("*") == 0) || (stck2[top]->compare("/") == 0))
                return 2;
        if ((stck2[top]->compare("+") == 0) || (stck2[top]->compare("-") == 0))
                return 1;
}

stack2::stack2()
{
	top = 0;
}

int stack2::isempty()
{
	return !top?1:0;
}

int stack2::isfull()
{
	return (top == MAXSIZE)?1:0;
}
	
void stack2::push(std::string* opertor)
{
	if (isfull()) {
		cout<<"stack full\n"<<endl;
                exit(1);
	} else {
		top++;
		stck2[top] = new std::string;
		stck2[top]->assign(opertor->c_str());
	}
}

std::string* stack2::pop()
{
	std::string *ret;
	if (isempty()) {
		cout<<"stack empty\n"<<endl;
	} else {
		ret = stck2[top--];
		return ret;
	}
}
/*========= operator stack ends ==============*/

/* General check on the range of number according the document */
int check_range(double number)
{
        if (number > 9999999 || number < -9999999) {
                std::cout<<"Number out of range. only till 9,999,999 allowed"<<endl;
		return -1;
        }
	
}
/* parse() function sets one "negative" variable if "-" occurs at the start of the input string or just next to some other
 * operator. That means the number following it is negative.
 * for e.g.
 * -3 + 2 => here (-3) is negative and "-" occured at the start
 *  4 + 9 * - 2 +? here (-2) is negative and "-" occured just next to other operator i.e. "*"
 */
int negate_if_applicable(int *negative, double *number)
{
        if(*negative) {
                *number = *number * -1;
                *negative = 0;
        }
        if(check_range(*number) == -1)
		return -1;
	return 0;
}

int is_numeric(std::string str)
{
        char *end;

        if(str.c_str() == NULL || str.length() == 0)
                return 0;

        strtod(str.c_str(), &end);
        if (*end == '\0') {
                return 1;
	} else {
                return 0;
	}
}
/* check if the word is either
 * - "hundred" then return 1
 * - "thosand" then return 2
 *  - "million" then return 3
 */
int check_htm(std::string str)
{

        if (str.compare("hundred") == 0 )
                return 1;
        else if (str.compare("thousand") == 0 )
                return 2;
        else if (str.compare("million") == 0 )
                return 3;
        else return 0;
}

void pack_for_postfix(struct queue_node *number_for_queue, double number, int type)
{
        number_for_queue->value.number = number;
        number_for_queue->type = type;
}

int precedence(std::string* opertor)
{
        if ((opertor->compare("*") == 0) || (opertor->compare("/") == 0))
                return 2;
        if ((opertor->compare("+") == 0) || (opertor->compare("-") == 0))
                return 1;
}
/* part of the postfix generation algorithms.
 * When at the end of input string, and there are still some operators on operator stack
 * enqueue them all on the postfix queue */
void queue_all_operators_to_postfix(stack2& xstack2, queue& xqueue)
{
        struct queue_node node;
        std::string* opertor;
	while (!xstack2.isempty()) {
                node.value.opertor = xstack2.pop();
                node.type = 2;
                xqueue.enqueue(node);
        }
}
/* main function which generates postfix generation 
 * this function gets called only with the opertaors only. For operands we queue them directly from parse() function.
 * Algorithm to generate postfix queue:
 * if (scanned token is an operand)
 * 	enqueue it directly on postfix queue. (this is done in parse() function itself 
 * 	in calls like xqueue.enqueue(number_for_queue);
 * if (scanned token is an operator)   
 * 	if ( operator stack is empty )
 *      	push the scanned operator on stack
 *	else ( if scanned operator's precedence is LESS THAN OR EQUAL to operator on top of stack
 *      	pop the operator from top of operator stack and queue it on postfix queue
 *	      and push the scanned operator on stack
 *	else (if scanned operator's precedence is greater than operator on top of stack)
 * 		push the operator on stack
 */
void generate_postfix_queue(stack2& xstack2, queue& xqueue, std::string* opertor)
{
	struct queue_node node;
	std::string* opertor1;
	if (xstack2.isempty())
		xstack2.push(opertor);
	else if (xstack2.precedence_of_top() >= precedence(opertor)) {
			node.value.opertor = xstack2.pop();
			node.type = 2;
			xqueue.enqueue(node);

		xstack2.push(opertor);
	} else {
		xstack2.push(opertor);
	}
}

/* this function parses each word out of the input string. 
 * 1. it checks if the word is digit (in is_numeric)
 * if yes get the number and skip to end (NXT)
 *
 * 2. Checks if the word is among "hundred", "thousand", "million"
 * 	if yes multiplies the number mentioned in word before it appropriately
 * 	i.e. if word is like "nine thousand" it multiplies nine by 1000
 * 	and store it in number_<hundred/thousand/million> variable
 * skip to end (NXT)
 *
 * 3. words like "by", "with", "and" are skipped
 *      they can come like "multiply by" "divide with" " two hundred and ten"
 *      no real benefit in matching them as we already match other words around them. 
 *      This is just to make the caculator more english friendly
 * skip to end (NXT)
 *
 * 4. checks if word is 
 *    "multiply" or "*"
 *    or 
 *    "divide" or "/"
 *    or 
 *    "plus" or "+"
 *    or
 *    "minus" or "-"
 *
 *    then
 *   a.  adds all number_<hundred/thousand/million> to number to get whole number before the "*" operator.
 *       for e.g. if we have statement like "nine thousand two hundred and three * one"
 *       number_thousand = 9000
 *       number_hundred  = 200
 *       number          = 3
 *       and at the end number = 9203
 *
 *    b. negate the number if applicable (see negate_if_applicable() for more info
 *
 *    c. set all the fields of node to enqueue it in postfix queue. 
 *       - set type = 1 as this is always called when the token is number 
 *          (we queue the operands in generate_postfix_queue() function. 
 *          See info of generate_postfix_queue() for more details
 *       -  reset all number_<hundred/thousand/million> and number variable to make them usable for next word.
 *       - set the prev_operator location needed for negate_if_applicable function.
 *         this is also used to find a syntax error if there are two operator adjacent to each 
 *         other like "* *" or "/ /". for e.g. "2 / / 3" is not a valid input.
 *
 *       - send appropriately filled temp_str with either "*", "/", "+", "-" to queue them in postfix queue 
 *         according to algorithm mentioned in generate_postfix_queue();
 * skip to end (NXT)
 *
 *  5. if all above conditions fail. it tries to find out the word in hash_table. numeric words lik "one" "ten" "twenty" 
 *     are put in hash table according to their length. (see hash_t() constructor for more info.
 * if we find the match skip to end (NXT)
 *
 *  6. if we are still not able to find any match then its a syntax error.
 *
 * NXT: 
 *  7. if the token is last token we don't have operator after it to make this number queue in postfix queue.
 *  numbers are queues to postfix queue only in step 4.
 * 
 * returns -1 if there is a syntax error
 */

int parse(expression& exp, hash_t& hash, queue& xqueue, stack2& xstack2)
{

	int i = 0, j = 0;
	double number = 0, number_hundred = 0, number_thousand = 0, number_million = 0;
	double number_temp = 0;
	int prev_opertor_location = -1;
	int negative = 0;
	int last_token = 0;
	struct queue_node number_for_queue;
	int switch_htm;
	std:string temp_str;
	
	for(i = 0; i < exp.no_of_words;i++) {
			
		if (i == exp.no_of_words -1 )
			last_token = 1;
		
		if(is_numeric(exp.word[i])) {
			number = atol(exp.word[i].c_str());
			if(check_range(number) == -1)
				return -1;
			goto NXT;
		}
			
		if ((switch_htm = check_htm(exp.word[i])) != 0) {
			switch(switch_htm) {
			case 1:
				number = number * 100;
				number_hundred += number;
				break;
			case 2:
				if (number_hundred) {
					number = number_hundred + number;
					number_hundred = 0;
				}
				number = number * 1000;
				number_thousand += number;
				break;
			case 3:
				if ( i > 1 ) {
					cout<<"Number out of range. only till 9,999,999 allowed\n"<<endl;
					return -1;
				}
				number = number * 1000000;
				number_million += number;
				if(check_range(number) == -1)
					return -1;
				break;
			}
			number = 0;
			goto NXT;
		}

		if ((exp.word[i].compare("and") == 0) || (exp.word[i].compare("with") == 0) || (exp.word[i].compare("by") == 0)) {
			goto NXT;
		}

		if ((exp.word[i].compare("divide") == 0 ) || (exp.word[i].compare("/")== 0)) {
                        number = number_million + number_thousand + number_hundred + number;
                        if(negate_if_applicable(&negative, &number) == -1)
				return -1;
                        pack_for_postfix(&number_for_queue, number, 1);
                        xqueue.enqueue(number_for_queue);
                        number_million = number_thousand = number_hundred = number = 0;

			if (prev_opertor_location == i - 1) {
				cout << "Syntax error before" << exp.word[i] << "\n";
				return -1;
			}
                        prev_opertor_location = i;
			temp_str.assign("/");
                        generate_postfix_queue(xstack2, xqueue, &temp_str);
                        goto NXT;
                }
		if ((exp.word[i].compare("multiply") == 0 ) || (exp.word[i].compare("*")== 0)) {
			number = number_million + number_thousand + number_hundred + number;
                        if(negate_if_applicable(&negative, &number) == -1)
				return -1;
			pack_for_postfix(&number_for_queue, number, 1);
			xqueue.enqueue(number_for_queue);
			number_million = number_thousand = number_hundred = number = 0;

			if (prev_opertor_location == i - 1) {
				cout << "Syntax error before" << exp.word[i] << "\n";
				return -1;
			}
			prev_opertor_location = i;
			temp_str.assign("*");
                        generate_postfix_queue(xstack2, xqueue, &temp_str);
			goto NXT;
		}
		if ((exp.word[i].compare("plus") == 0) || (exp.word[i].compare("+")== 0)) {
			number = number_million + number_thousand + number_hundred + number;
                        if(negate_if_applicable(&negative, &number) == -1)
				return -1;
			pack_for_postfix(&number_for_queue, number, 1);
			xqueue.enqueue(number_for_queue);
			number_million = number_thousand = number_hundred = number = 0;

			if (prev_opertor_location == i - 1) {
				cout << "Syntax error before" << exp.word[i] << "\n";
				return -1;
			}

			prev_opertor_location = i;
			temp_str.assign("+");
                        generate_postfix_queue(xstack2, xqueue, &temp_str);
			goto NXT;
		}
		if ((exp.word[i].compare("minus") == 0) || (exp.word[i].compare("-") == 0)) {
			/* is it an actualy opertor or just a sign*/
			/* this can be found out if 
			 * "-" token is the first token
			 * there was an opertor before this "-" token */
			
			/* Set prev_opertor_location everytime an opertor is encountered */
			if (prev_opertor_location == i - 1) {
				negative = 1;
				goto NXT;
			}
			number = number_million + number_thousand + number_hundred + number;
                        if(negate_if_applicable(&negative, &number) == -1)
				return -1;
			pack_for_postfix(&number_for_queue, number, 1);
			xqueue.enqueue(number_for_queue);
			number_million = number_thousand = number_hundred = number = 0;
			prev_opertor_location = i;
			temp_str.assign("-");
                        generate_postfix_queue(xstack2, xqueue, &temp_str);
			goto NXT;
		}
		if ((exp.word[i].length() >= 3) && (exp.word[i].length() <= 9)) {
			if((number_temp = hash.find_string_in_hash_table(exp.word[i])) > 0) {
				number += number_temp;
				goto NXT;
			}
		}

		cout << "Syntax error near \""<< exp.word[i]<<"\"\n";
		if ((exp.word[i].compare("(") == 0)) {
			cout << "\nNote: Brackets not allowed\n";
		}
		cout << "type \"help\" for more info";
		return (-1);
	NXT:
		if (last_token) { 
			number = number_million + number_thousand + number_hundred + number;
                        if(negate_if_applicable(&negative, &number) == -1)
				return -1;
			pack_for_postfix(&number_for_queue, number, 1);
			xqueue.enqueue(number_for_queue);
			queue_all_operators_to_postfix(xstack2, xqueue);
		}
	}
}
/* solve the postfix expression queue.
 * Algorithm:
 * do folloqing until postfix queue is not empty {
 *	 if (front of the queue is operand (number))
 * 		 push it to operand stack
 *	 else if (front of the queue is operator (+,/,-,+))
 *      	operand1 = pop from operand stack
 *	      operand2 = pop from operand stack
 *
 *		solve operand2 "operator(from front of queue)" operand
 *
 *		put the result on top of operand stack
 *}
 * last number on top of operand stack is our result. 	
 */
double solve_the_postfix(queue xqueue, stack xstack)
{
        double operand1, operand2, result;
        int i;

	struct queue_node qnode;
	std::string *opertor;
	while (!xqueue.isempty()) {
		qnode = xqueue.dequeue();
		if(qnode.type == 1) {
			xstack.push(qnode.value.number);
		} else if (qnode.type == 2) {
			operand1 = xstack.pop();
			operand2 = xstack.pop();
			if (qnode.value.opertor->compare("+") == 0) {
				result = operand2 + operand1;
			} else if (qnode.value.opertor->compare("-") == 0) {
				result = operand2 - operand1;
			} else if (qnode.value.opertor->compare("*") == 0) {
				result = operand2 * operand1;
			} else if (qnode.value.opertor->compare("/") == 0) {
				result = operand2 / operand1;
			}
			delete qnode.value.opertor;
		xstack.push(result);
		}
	}
	return xstack.pop();
}

int main()
{
	string input = "";
	int ret;
	char str[100];
	int i;
	cout << "\nInput a string and press return when you done\n";
	cout << "Note: Type \"help\" for help. \"quit\" to quit\n";
	do {
		hash_t hash;
		stack operand;
		stack2 opertor;
		queue queue1;
		std::cout << "\n===================\n";
		cout << "Input: ";
		getline(cin, input);
		if ((input.compare("quit")) == 0) {
			cout << "Bye!\n";
			exit(1);
		}
		if (((input.compare("h")) == 0) || ((input.compare("help")) == 0)) {
			cout << "\nHelp:\n";
			cout << "Give input string in either words or digits. ";
			cout << "For e.g. \"two plus three\" or \"2 + 3\"\n";
			cout << "Note:Mixing of words and number are allowed upto some extent";
			cout << " but no gurantee.\n\n";
			cout << "If you are writing expression in words:\n";
			cout << "- Numbers like 223 have to be written like \"two hundred twenty three.\"\n";
			cout << "- English short forms like \"two zero three\" or \" two twenty three\" not allowed.\n";
			cout << "- No brackets allowed.\n";
			continue;
		}			
		strcpy(str,input.c_str());
		expression exp(str);
		if ((ret = parse(exp, hash, queue1, opertor)) == -1)
			continue;
		std::cout << "\nResult: ";
		std::cout << solve_the_postfix(queue1, operand);
	} while (1);
}
